package com.fyl.leetcode.backtracking;

import com.fyl.leetcode.DFS.isLand.LargestIsland;

import java.util.ArrayList;
import java.util.List;

/**
 * @author:fyl
 * @date 2021/7/30 8:43
 * @Modified By:
 * @Modified Date:
 * @Description: 216
 * 找出所有相加之和为n 的k个数的组合。组合中只允许含有 1 -9 的正整数，并且每种组合中不存在重复的数字。
 * <p>
 * 说明：
 * <p>
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1:
 * <p>
 * 输入: k = 3, n = 7
 * 输出: [[1,2,4]]
 * <p>
 * 输入: k = 3, n = 9
 * 输出: [[1,2,6], [1,3,5], [2,3,4]]
 */
public class CombinationSumIII {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, new ArrayList<>(), k, 1, n);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) {
        if (list.size() == k || n <= 0) {
            if (list.size() == k && n == 0) {
                res.add(new ArrayList<>(list));
            }
            return;
        }

        for (int i = start; i <= 9; i++) {
            list.add(i);
            dfs(res, list, k , i + 1, n - i);
            list.remove(list.size() - 1);
        }
    }
}
